package Gather.DataStructure;

/**
 * ClassName:Tree001
 * Package:Gather.DataStructure
 * Description:
 *
 * @Author:ZhangXin
 * @Create2023/2/8-16:56
 * @Version:v1.0
 */
public class Tree001 {
    /*树(节点->Node)
    *
    *      父节点
    * 左子节点  右子节点
    *
    * 度：每一个节点的子节点数量
    * 二叉树,任意节点的度<=2
    * 树高：树的总层数
    * 根节点：最顶层的节点
    *
    * 普通二叉树
    *
    * 二叉查找树：又称二叉排序树或者二叉搜索树
    * 特点：
    * 1.每一个节点上最多有两个节点
    * 2.任意节点左子树上的值都小于当前节点
    * 3.任意节点右子树上的值都大于当前节点
    *
    *  添加节点规则：(小的存左边,大的存右边,一样的不存)
    *
    * 二叉树的遍历方式：
    * 1.前序遍历：从根结点开始,然后按照当前结点,左子结点,右结点的顺序遍历
    * 2.中序遍历(左中右)：从最左边的子节点开始,然后按照左子结点,当前结点,右子结点的顺序遍历
    * 3.后序遍历(左右中)：从最左边的子节点开始,然后按照左子结点,右子结点,当前结点的顺序遍历
    * 4.层序遍历：从根节点开始一层一层遍历
    *
    *
    * 平衡二叉树(高度会导致二叉树不平衡)
    * 规则：任意节点左右子树高度差不超过1
    *
    * 平衡二叉树保持平衡的机制---旋转机制
    *
    * 规则1：左旋(确定支点：从添加的节点开始,不断往父节点找不平衡的节点)
    * 步骤：
    * 1.以不平衡的点作为支点
    * 2.把支点左旋降级,变成左子节点
    * 3.晋升原来的右子节点
    *
    * 规则2：右旋(确定支点：从添加的节点开始,不断往父节点找不平衡的节点)
    * 步骤：
    * 1.以不平衡的点作为支点
    * 2.把支点右旋降级,变成右子节点
    * 3.晋升原来的左子节点
    *
    *
    * 添加结点导致二叉树不平衡的四种情况
    * 1.左左(一次右旋)：当根节点左子树的左子树有节点插入,导致二叉树不平衡
    * 2.左右(先局部左旋,然后整体右旋)：当根节点左子树的右子树右结点插入,导致二叉树不平衡
    * 3.右右(一次左旋)：当根节点右子树的右子树有节点插入,导致二叉树不平衡
    * 4.右左(先局部右旋,然后整体左旋)：当根节点右子树的左子树有节点插入,导致二叉树不平衡
    * */
}
